package algorithms;

/**
 * 
 * @author Emanuel Martins 5940, Ana Pontes 5950 || date 05/06/2014
 * 
 *         This is the class QuickSort, this class is a sorting algorithm.
 * 
 */

public class QuickSort
{

   /**
    * This method does a quick sort
    * 
    * @param A
    *           - array of int
    */

   public QuickSort(int[] A)
   {
      final int p = 0;
      int r = A.length - 1;
      run(A, p, r);
   }

   /**
    * This method does the exchange of the sorting
    * 
    * @param A
    *           - array of int
    * @param i
    *           - first value
    * @param j
    *           - second value
    */

   private void exchange(int[] A, int i, int j)
   {
      int temp = A[i];
      A[i] = A[j];
      A[j] = temp;
   }

   /**
    * This method
    * 
    * @param A
    *           - array of int
    * @param p
    *           - value of partition
    * @param r
    *           - value of run
    */

   public void run(int[] A, int p, int r)
   {
      if (p < r)
      {
         int q = partition(A, p, r);
         run(A, p, q - 1);
         run(A, q + 1, r);
      }
   }

   /**
    * This method does a partition of the sort
    * 
    * @param A
    *           - array of int
    * @param p
    *           - value of partition
    * @param r
    *           - value of run
    * 
    */

   private int partition(int[] A, int p, int r)
   {
      int x = A[r];
      int i = p - 1;
      for (int j = p; j <= r - 1; j++)
      {
         if (A[j] <= x)
         {
            i = i + 1;
         }
         exchange(A, i, j);
      }
      exchange(A, i + 1, r);
      return i + 1;
   }
}